package features.advance.leetcode.array.easy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *  剑指 Offer 57 - II. 和为s的连续正数序列
 *
 *  难度：简单
 *
 * 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
 *
 * 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
 *
 *
 *
 * 示例 1：
 *
 * 输入：target = 9
 * 输出：[[2,3,4],[4,5]]
 * 示例 2：
 *
 * 输入：target = 15
 * 输出：[[1,2,3,4,5],[4,5,6],[7,8]]
 *
 *
 * 限制：
 *
 * 1 <= target <= 10^5
 *
 * @author LIN
 * @date 2021-05-31
 */
public class Offer57_2 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
            @Override
            public int[][] findContinuousSequence(int target) {
                List<int[]> vec = new ArrayList<int[]>();
                for (int l = 1, r = 2; l < r;) {
                    int sum = (l + r) * (r - l + 1) / 2;
                    if (sum == target) {
                        int[] res = new int[r - l + 1];
                        for (int i = l; i <= r; ++i) {
                            res[i - l] = i;
                        }
                        vec.add(res);
                        l++;
                        r++;
                    } else if (sum < target) {
                        r++;
                    } else {
                        l++;
                    }
                }
                return vec.toArray(new int[vec.size()][]);
            }
        };
        int target = 15;
        solution = new Solution(){
            @Override
            public int[][] findContinuousSequence(int target) {
                if(target<3){
                    return null;
                }
                List<int[]> vec = new ArrayList<int[]>();
                for(int i=(int)Math.sqrt(2*target);i>=2;i--){
                    if((2*target - i*(i-1)) % (2*i) == 0){// 求解出第一项，i是项数
                        int[] temp = new int[i];
                        for(int j = 0; j<i;j++){
                            temp[j]=(2*target - i*(i-1)) / (2*i) + j;
                        }
                        vec.add(temp);
                    }
                }
                return vec.toArray(new int[vec.size()][]);

            }
        };
        int[][] continuousSequence = solution.findContinuousSequence(target);

        for (int[] ints : continuousSequence) {
            System.out.print(Arrays.toString(ints));

        }
    }

    static class Solution{
        /**
         *  思路；
         * @param target
         * @return
         */
        public int[][] findContinuousSequence(int target) {
            List<int[]> vec = new ArrayList<int[]>();
            int sum = 0, limit = (target - 1) / 2; // (target - 1) / 2 等效于 target / 2 下取整
            for (int i = 1; i <= limit; ++i) {
                for (int j = i;; ++j) {
                    sum += j;
                    if (sum > target) {
                        sum = 0;
                        break;
                    } else if (sum == target) {
                        int[] res = new int[j - i + 1];
                        for (int k = i; k <= j; ++k) {
                            res[k - i] = k;
                        }
                        vec.add(res);
                        sum = 0;
                        break;
                    }
                }
            }
            return vec.toArray(new int[vec.size()][]);
        }
    }
}
